package com.yjc.dp;

/**
 * 面试题 08.01. 三步问题
 *
 * @author yjc
 * @create 2024-07-25 9:21
 */
public class Subject_11 {
    public static void main(String[] args) {
        int n = 61;

        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            if (i < 4) {//前三层，由于1、2、3层都可一次跨越，所以前三层需要+1额外补充一次方法
                switch (i) {
                    case 1:
                        dp[i] = dp[i - 1] + 1;
                        break;
                    case 2:
                        dp[i] = dp[i - 2] + dp[i - 1] + 1;
                        break;
                    case 3:
                        dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1] + 1;
                        break;
                }
            } else {//第四层开始，最少要登上一层楼梯才能一次跨越至顶层，都是状态转移，所以不需要额外补充方法次数
                dp[i] = (((dp[i - 3] + dp[i - 2]) % 1000000007) + dp[i - 1]) % 1000000007;//两次取模防止值溢出
            }
        }
        System.out.println(dp[n]);

    }
}
